This application claims priority to International Application No. PCT/DE99/02536 which was published in the German language on Aug. 13, 1999.
The present invention relates to a method and apparatus for computer-aided pipette selection for a placement head of an automatic placement machine, and in particular for allocation of components to the pipette types provided in a pipette selection.
A method for checking the so-called consecutive ones characteristic, is described in W. L. HSU, A Simple Test for the Consecutive Ones Property, Lecture Notes in Computer Science: Algorithms and Computation, Vol. 650, pages 459-468, 1992. If the consecutive ones characteristic is present, then the method implicitly provides all the permissible associations to component types.
Various types of placement heads are normally used. One such placement head is, for example, the so-called SP head (Speed Placer-head), by means of which a number of components can be picked up from the component store, transported and successively placed on the printed circuit board.
An SP placement head has a number of segments, (normally 6 or 12 segments), to each of which a pipette can be fitted. The pipettes allow components to be picked up and placed in position. There are various pipette types by means of each of which different types of components can be placed in position. The process of populating a printed circuit board with components by means of an SP placement head normally takes place in a number of iterations (cycles), in each of which the placement head first of all picks up as a maximum the number of components which can be processed and then places them down on the printed circuit board in the same sequence in which it picked them up. The time which is required for one cycle depends only to a minor extent on the number of components picked up and placed in position in this cycle, so that the smallest possible number of cycles for the placement process is the most time-critical criterion relating to the population process.
It is thus desirable to pick up and place in position as many components as possible in the individual cycles, that is to say to avoid xe2x80x9cgapsxe2x80x9d in the placement process, in association thus to minimize the number of cycles required to place all the components in position.
A method for checking the so-called consecutive ones characteristic, is described in [1]. If the consecutive ones characteristic is present, then the method from [1] implicitly provides all the permissible associations to component types.
A method for checking the so-called acyclic hypergraph characteristic, which has a linear complexity, is described in R. E. Taijan, M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM J, Comput., Vol. 13, pages 566-579, 1984.
A method for solving a flow problem is described in R. K. Ahuja et al., Network Flows, Prentice Hall, pages 207-242 and 255-258, 1993.
A so-called branch and cut method for optimum solution of an integer linear program is described in G. L. Nemhauser, L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, N.Y., pages 349-379, 1988.
In one embodiment of the invention, there is a method for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to different pipette types predetermined in a pipette selection for a given number of cycles z. The method using, a stored component type list B with a respectively associated number of components of the component type to be placed, a component type association based on the component types, a stored pipette type list P of available pipette types and an allocation list E which indicates which component types can be placed using what pipette types, and based on the component type association for the pipette types pxcex5P, a pipette type association is formed in such a manner that p1xe2x89xa6p2xe2x86x92(1(p1) less than 1(p2)) v ((1(p1)=1(p2)){circumflex over ( )}f(p1)p2))), where p1, p2xcex5P denote different pipette types, 1(p), pxcex5P, is defined by 1(p)=max{bxcex5B|(b, p)xcex5E}, f(p), pxcex5P, is defined by f(p)=min{bxcex5B|(b, p)xcex5E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z, if any components of this component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In one aspect of the invention, there is a method for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to the pipette types predetermined in a pipette selection for a given number of cycles z, in which, using a stored component type list B with a respectively associated number of components of the component type to be placed, a stored pipette type list P of available pipette types and an allocation list E which indicates which component types can be placed using what pipette types, determining whether a permissible component type association by carrying out a check, such that (b1, p)xcex5E, (b2, p)xcex5E, b1xe2x89xa6bxe2x89xa6b2xe2x86x92(b, p)xcex5E, where b1, b2, b components in the component type list B are denoted, (b, p)xcex5E, bxcex5B , pxcex5P, denotes the situation where a component of component type b can be placed using a pipette of pipette type p, in which, based on the permissible component type association for the pipette types pxcex5P, a pipette type association is formed in such a manner that, p1xe2x89xa6p2xe2x86x92(1(p1)xe2x89xa61(p2))v((1(p1)=1(p2)){circumflex over ( )}f(p1)xe2x89xa7f(p2))), where p1, p2xcex5P denote different pipette types, 1(p), pxcex5P, is defined by 1(p)=max{bxcex5B|(b, p)xcex5E}, f(p), pxcex5P, is defined by f(p)=min{bxcex5B|(b, p)xcex5E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then the pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z; if any components of the component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and, in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In another aspect of the invention, in the situation where no permissible component type association exists, the allocation list E is reduced in size, based on the component types and the pipette types, as many components as possible are allocated successively for each pipette type to the respective pipette type so that a component type association to the component types exists for the resultant allocation list E in such a manner that: (b1, p)xcex5E, (b2, p)xcex5E, b1xe2x89xa6bxe2x89xa6b2xe2x86x92(b, p)xcex5E, in which, for the pipette types pxcex5P a pipette type association is formed in such a manner that: P1xe2x89xa6P2xe2x86x92(1(P1) less than 1(P2))v((1(P1)=1(P2)){circumflex over ( )}f(P1)xe2x89xa7f(P2))), in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z; if any components of this component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and, in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In still another aspect of the invention, in the situation where no permissible component type association exists, the solution to be determined is found by solving a sequence of flow problems.
In yet another aspect of the invention, in the situation where no permissible component type association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list E, so that each sub-graph, which is induced from a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, and if such a set of trees can be determined, the solution to be determined is found by solving a sequence of flow problems.
In another aspect of the invention, the situation where no permissible association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list, so that each sub-graph, which is induced by a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, if such a set of trees cannot be determined, elements are deleted from the allocation list E until such a set of trees can be determined, and the solution to be determined is found by solving a sequence of flow problems.
In yet another aspect of the invention, the sequence of flow problems is formed in accordance with the following rules, xcexa3xbp=nb p:(b,p)xcex5E ∀bxcex5B xcexa3xbpxe2x89xa6cp p:(b,p)xcex5E ∀pxcex5P, nb indicates a number of components of the component type bxcex5E to be placed, cp, pxcex5P denotes a window which can be predetermined and which is varied in association to form the sequence of flow problems, a first solution variable xbp indicates how many components of the component type bxcex5B are placed by a pipette of the pipette type pxcex5P.
In still another aspect of the invention, in the situation where no permissible association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list, so that each sub-graph, which is induced by a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, and in which, if no such set of trees can be determined, the solution to be determined is found by solving a linear program.
In another aspect of the invention, in which the linear program is formed in accordance with the following rules: nb indicates a number of components of the component type bxcex5E to be placed, a first solution variable xbp indicates how many components of the component type bxcex5B are placed by a pipette of the pipette type pxcex5P, a second solution variable yp indicates how many pipettes of the pipette type pxcex5P are selected, k denotes a number of segments of the placement head, and x,yxe2x89xa70 is an integer.
In still another aspect of the invention, the linear program is solved using a branch and cut method.
In yet another aspect of the invention, which is carried out a number of times for a different number of cycles in each case.
In another aspect of the invention, in which the pipettes which have been determined are allocated to the placement head, and the components are placed on a printed circuit board using the placement head.
In another embodiment of the invention, there is an apparatus for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to different pipette types predetermined in a pipette selection for a given number of cycles z, comprising a memory for storing a component type list B, a pipette type list B and an allocation list E; and a processor which is coupled to the memory and stores the following for processing the stored component type list B with the respectively associated number of components of the component type to be placed, a component type association for the component types, a stored pipette type list P of available pipette types and the allocation list E which indicates which component types can be placed by what pipette types, and based on the component type association for the pipette types pxcex5P, a pipette type association is formed in such a manner that:p1xe2x89xa6p2xe2x86x92(1(p1) less than 1(p2))v((1(p1)1(p2)){circumflex over ( )}f(p1)xe2x89xa7f(p2))), where p1, p2xcex5P denote different pipette types, 1(p), pxcex5P, is defined by 1(p)=max{bxcex5B|(b, p)xcex5E}, f(p), pxcex5P, is defined by f(p)=min{bxcex5B|(b, p)xcex5E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner. If for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then the pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z, if any components of this component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and, in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In still another embodiment of the invention, an apparatus for computer-aided pipette selection for a placement head of an automatic placement machine and for allocation of components to the pipette types predetermined in a pipette selection for a given number of cycles z, comprising, a memory for storing a component type list B, a pipette type list B and an allocation list E; and a processor which is coupled to the memory and stores the following for processing, a stored component type list B with the respectively associated number of components of the component type to be placed, a stored pipette type list P of available pipette types and an allocation list E which indicates which component types can be placed by what pipette types, a check is carried out to determine whether a permissible component type association exists, such that (b1, p)xcex5E, (b2, p)xcex5E, b1xe2x89xa6bxe2x89xa6b2xe2x86x92(b, p)xcex5E, where b1, b2, b components in the component type list B are denoted, (b, p)xcex5E, bxcex5B , pxcex5P, denotes the situation where a component of component type b can be placed using a pipette of pipette type p, in which, based on the permissible component type association for the pipette types pxcex5P, a pipette type association is formed in such a manner that, p1xe2x89xa6p2xe2x86x92(1(p1) less than 1(p2))v((1(p1)=1(p2)){circumflex over ( )}f(p1)xe2x89xa7f(p2))), where p1, p2xcex5P denote different pipette types, 1(p), pxcex5P, is defined by 1(p)=max{bxcex5B|(b, p)xcex5E}, f(p), pxcex5P, is defined by f(p)=min{bxcex5B|(b, p)xcex5E}, in which the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then the pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z, if any components of this component type remain, then the remaining components are allocated to the last possible pipette type based on the pipette type association and, in which the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected.
In another aspect of the invention, the processor is set up in such a manner that in the situation where no permissible component type association exists, the allocation list E is reduced in size and based on the component types and the pipette types, as many components as possible are allocated successively for each pipette type to the respective pipette type so that a component type association to the component types exists for the resultant allocation list E in such a manner that, (b1, p)xcex5E, (b2, p)xcex5E, b1xe2x89xa6bxe2x89xa6b2xe2x86x92(b, p)xcex5E, in which, for the pipette types pxcex5P a pipette type association is formed in such a manner that, P1xe2x89xa6P2xe2x86x92(1(P1) less than 1(P2))v((1(P1)=1(P2)){circumflex over ( )}f(P1)xe2x89xa7f(P2))), the components are successively allocated to the pipette types, in a sequence which results from the component type association, in the following manner, if, for a component type, pipette types exist to which any given multiple of the number of cycles z of large numbers of components are not already allocated, then pipette types are first allocated to components on the basis of the pipette type association, in such a manner that the number of allocated components is rounded up to the next multiple of the number of cycles z; if any components of this component type remain, then the remaining components re allocated to the last possible pipette type based on the pipette type association and, the number of components allocated to one pipette type is used to determine the number of pipettes of that pipette type to be selected. In still another aspect of the invention, in which the processor is set up in such a manner that in the situation where no permissible component type association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list E, so that each sub-graph, which is induced from a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, and if such a set of trees can be determined, the solution to be determined is found by solving a sequence of flow problems.
In yet another aspect of the invention, in which the processor is set up in such a manner that in the situation where no permissible association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list, so that each sub-graph, which is induced by a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, if such a set of trees cannot be determined, elements are deleted from the allocation list E until such a set of trees can be determined, and the solution to be determined is found by solving a sequence of flow problems.
In another aspect of the invention, in which the processor is set up in such a manner that the sequence of flow problems is formed in accordance with the following rules, xcexa3xbp=nb p:(b,p)xcex5E ∀bxcex5B xcexa3xbpxe2x89xa6cp p:(b,p)xcex5E ∀pxcex5P, nb where nb indicates a number of components of the component type bxcex5E to be placed, cp, pxcex5P denotes a window which can be predetermined and which is varied in association to form the sequence of flow problems, a first solution variable xbp indicates how many components of the component type bxcex5B are placed by a pipette of the pipette type pxcex5P.
In yet another aspect of the invention, in which the processor is set up in such a manner that in the situation where no permissible association exists, a check is carried out to determine whether a set of trees with the pipette types as nodes of the trees can be determined for possible allocations of the component types to the pipette types in accordance with the allocation list, so that each sub-graph, which is induced by a set of pipette types P(b) which can place a component b, in the set of trees is cohesive, and if such a set of trees cannot be determined, the solution to be determined is found by solving a linear program as the possible allocations are formulated.
In still another aspect of the invention, in which the processor is set up in such a manner that the linear program is formed in accordance with the following rules, xcexa3xbp=nb p:(b,p)xcex5E ∀bxcex5B xcexa3xbpxe2x89xa6yp z p:(b,p)xcex5E ∀pxcex5P xcexa3ypxe2x89xa6k pxcex5P, nb where nb indicates a number of components of the component type bxcex5E to be placed, a first solution variable xbp indicates how many components of the component type bxcex5B are placed by a pipette of the pipette type pxcex5P ; a second solution variable yp indicates how many pipettes of the pipette type pxcex5P are selected, k denotes a number of segments of the placement head, and x,yxe2x89xa70 is an integer.
In another aspect of the invention, in which the processor is set up in such a manner that the method is carried out for a different number of cycles in each case.
In still another aspect of the invention, an automatic placement machine having an apparatus as claimed in claim 13 further comprising, a component memory for the component, a placement head for picking up pipettes, at least one pipette for picking up components, a placement device for placing the components on a printed circuit.
In yet another aspect of the invention, the method is carried out a number of times for a different number of cycles in each case.
In another aspect of the invention, in which the pipettes which have been determined are allocated to the placement head, and the components are placed on a printed circuit board using the placement head.
In still another aspect of the invention, in which the processor is set up in such a manner that the method is carried out for a different number of cycles in each case.
In yet another aspect of the invention, a, automatic placement machine having an apparatus further comprising: a component memory for the component, a placement head for picking up pipettes, at least one pipette for picking up components, a placement device for placing the components on a printed circuit.